\begin{abstract}
 We study a new distributed randomized information propagation
 mechanism in networks that we call a {\em branching random walk
   (BRW)}.  BRW is a generalization of the well-studied ``standard"
 random walk which is a fundamental primitive useful in a wide variety
 of network applications ranging from token management and load
 balancing to search, routing, information propagation and gossip.
 BRW is parameterized by a {\em branching factor} $k$.  The process
 starts from an arbitrary node, which is labeled {\em active} for step
 $1$.  For instance, this could be a node that has a piece of data,
 rumor, or a virus. In a BRW, in any step, each active node chooses
 $k$ random neighbors to become active for the next step.  A node is
 active for step $t+1$ only if it is chosen by an active node in step
 $t$. This results in a branching type process in the underlying
 network which has interesting properties that are strikingly
 different from the standard random walk, which is equivalent to BRW
 with branching factor $k=1$. Similar to the standard random walk, we
 focus on the {\em cover time}, which is the the number of steps for
 the walk to reach all the nodes and the {\em partial cover time},
 which is the number of steps needed for the walk to reach at least a
 constant fraction of the nodes.

We derive almost-tight bounds on cover time and partial cover time in {\em expander} graphs, an important class 
of graphs that   arise in many distributed network applications, especially in the modeling and construction of peer-to-peer and overlay networks.  A main result of this paper
is that the time needed by a BRW for partial coverage in an $n$-node
bounded-degree expander is $O(\log n)$ (even with branching factor 2,
assuming sufficiently large expansion) and for full coverage is
$O(\log^2 n)$ with high probability. Since the cover time of standard
random walk is $\Theta(n \log n)$ in an expander, this shows that BRW
gives an exponential speedup.   

%Our BRW results can also be generalized
%to understand the time taken for an epidemic process in an SIS-type
%model to spread in a network.  
%While the persistence time and epidemic
%density of SIS-type epidemic models are well studied, here we analyze
%the time needed for a SIS-type process to reach partial coverage of a
%graph.  By manipulating the branching factor and the time
%that a node remains infected, the process can also be viewed as a
%generalized rumor spreading model, with applications in both
%epidemiology and information dissemination.
\end{abstract}
